//491.非递减子序列
//https://leetcode.cn/problems/non-decreasing-subsequences/
class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        int n = nums.size();
        vector<int> path;
        set<vector<int>> ret; //set去重 防止[1,2,3,1,1,1,1]情况
        //vector<vector<int>> ret;
        path.reserve(n);
        function<void(int)> dfs = [&](int idx){

            //if(path.size() > 1) ret.push_back(path);
            if(path.size() > 1) ret.insert(path);
            if(idx > n) return;

            for(int k = idx;k<n;++k)
            {
                if(nums[k] >= path.back())
                {
                    path.push_back(nums[k]);
                    dfs(k+1);
                    path.pop_back();
                    while(k+1<n && nums[k]==nums[k+1]) ++k;//去重
                }
            }
        };
        for(int i = 0;i<n;++i) //确定第一个数字
        {
            path.push_back(nums[i]);
            dfs(i+1);
            path.pop_back();
            while(i+1<n && nums[i]==nums[i+1]) ++i;//去重
        }

        return {ret.begin(),ret.end()};
    }
};